import math

class Node:
    name = " "
    x = 0
    y = 0
    Parent = None
    CostSoFar = 0
    FutureCost = 0

    def __init__(self,name,x,y):
        self.name = name
        self.x = x
        self.y = y
        

class Link:
    Distance = 0.0
    StartCity = ' '
    EndCity = ' '

    def __init__(self,StartCity,EndCity,Distance):
        self.StartCity = StartCity
        self.EndCity = EndCity
        self.Distance = Distance


class Graph:
    NodeList = []
    LinkList = []
    


    def NodeProcess(self,dataLine):
        mylist = []
        mylist = dataLine[:-1].split(";")
        #print(mylist)
        n = Node(mylist[0],mylist[1],mylist[2])
        self.NodeList.append(n)

    def RoadProcess(self,dataline):
         mylist = []
         mylist = dataline[:-1].split(";")
         searchlist1 = []
         searchlist1.append(self.SearchX(mylist[0]))
         searchlist1.append(self.SearchY(mylist[0]))
         searchlist2 = []
         searchlist2.append(self.SearchX(mylist[1]))
         searchlist2.append(self.SearchY(mylist[1]))
         distance = self.CalculateDistance(int(searchlist1[0]),int(searchlist1[1]),int(searchlist2[0]),int(searchlist2[1]))
         l = Link(mylist[0],mylist[1],distance)
         #print(mylist[0],mylist[1],distance);
         self.LinkList.append(l)



    def ReadLocations(self,fileName):
        dataFile = open(fileName)
        for dataLine in dataFile.readlines():
            self.NodeProcess(dataLine)
        dataFile.close()
        del dataFile

    def ReadRoads(self,fileName):
        dataFile = open(fileName)
        for dataLine in dataFile.readlines():
            self.RoadProcess(dataLine)
        dataFile.close()
        del dataFile
    
    def CalculateDistance(self,x1,y1,x2,y2):
        xtot = x2 - x1
        ytot = y2 - y1
        Distance = math.sqrt((xtot ** 2) + (ytot ** 2))
        return Distance

    def SearchX(self,Cityname):
        for node in self.NodeList:
            if(node.name == Cityname):
                return node.x
   
    def SearchY(self,Cityname):
        for node in self.NodeList:
            if(node.name == Cityname):
                return node.y



        #StartCity = ""
        #GoalCity = ""
        #input_var = input("Travel from: ")
        #StartCity = input_var
        #input_var = input("Travel to: ")
        #GoalCity = input_var

        #StartCity = "Ingolstadt"
        #GoalCity = "Neuburg"


    # STEGA IGENOM OCH TESTA VART DET BLIR FEL

    def AStar(self,StartCity,GoalCity):
        Frontier = []
        Explored = []

        for x in self.NodeList:
            if(x.name == StartCity):
                Frontier.append(x)
        Frontier[0].FutureCost = self.CalculateFutureCost(Frontier[0],GoalCity)
        del x


        while(len(Frontier) != 0):
            node = self.SelectBest(Frontier)
            if(node.name == GoalCity):
                return self.ReconstructPath(node,Explored)
            Frontier.remove(node)
            Explored.append(node)

            for x in self.GetNodeNeighbours(node):
                x.FutureCost = self.CalculateFutureCost(x,GoalCity)
                NewCost = self.CalculateCostSoFar(node,x)

                if x in Explored:
                    if(NewCost < x.CostSoFar):
                        x.CostSoFar = NewCost
                        x.Parent = node
                        Explored.remove(y)
                        Frontier.append(x)

                elif(x in Frontier):
                    x.CostSoFar = NewCost
                    x.Parent = node

                else:
                    x.CostSoFar = NewCost
                    x.Parent = node
                    Frontier.append(x)        


    def GetNodeNeighbours(self,node):
        Neighbours = []
        for x in self.LinkList:
            if(node.name == x.StartCity):
                for y in self.NodeList:
                    if(x.EndCity == y.name):
                        Neighbours.append(y)
        return Neighbours
                        
                                       
    def ReconstructPath(self,Node,Explored):
        CurrentNode = Node
        Path = []
        Path.append(CurrentNode.name)
        while(CurrentNode.Parent != None):
            for x in Explored:
                if(x == CurrentNode.Parent):
                    Path.append(x.name)
                    Explored.remove(x)
            CurrentNode = CurrentNode.Parent       
        Path.reverse()
        return Path


    def SelectBest(self,Frontier):
        return min(Frontier, key = lambda x: x.CostSoFar + x.FutureCost)
                 

    def CalculateFutureCost(self,Node,GoalCity):
        for x in self.NodeList:
            if (Node.name == x.name):
                for goal in self.NodeList:
                    if(GoalCity == goal.name):
                        H = self.CalculateDistance(int(x.x),int(x.y),int(goal.x),int(goal.y))
        return H;

    def CalculateCostSoFar(self,Node1,Node2):
        Distance = self.CalculateDistance(int(Node1.x),int(Node1.y),int(Node2.x),int(Node2.y))
        return Node1.CostSoFar + Distance
        
        


    


g = Graph()
g.ReadLocations("locations.csv")
g.ReadRoads("roads-1.csv")
print(str(g.AStar("Weichering","Denkendorf")))



